package org.xingole.leetcode.dp;

import java.util.Arrays;

/**
 * <a href="https://leetcode.com/problems/maximum-length-of-pair-chain/description/">
 * Problem Description
 * </a>
 */
public class MaximumLengthOfPairChain {
    public int findLongestChain(int[][] pairs) {
        // Define dp[i] as the length of the longest pair chain ending with pairs[i].
        int n = pairs.length;
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);

        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[i][0] > pairs[j][1]) {
                    if (pairs[i][0] > pairs[j][1]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
        }

        return dp[n - 1];
    }
}
